package samples.java.algorithm.stack;

/**
 * 用数组实现栈
 *
 * <p>
 * 1. 栈的insert操作被称为压入(push), delete操作被称为弹出(pop)
 * 2. dataElements表示数组, 属性top指向最新插入的元素, dataElements[0]是栈底元素, dataElements[top]是栈顶元素
 * </p>
 *
 * @author wang.yuchuan
 * @date 2018/1/16
 */
public class StackImpl<E> implements Stack<E> {

    /**
     * 用来存储栈元素的数组
     */
    private Object[] dataElements;

    /**
     * 指向最新插入的元素
     */
    private int top = 0;

    public StackImpl(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " +
                initialCapacity);
        this.dataElements = new Object[initialCapacity];
    }

    public StackImpl() {
        this(10);
    }

    /**
     * 栈元素的insert操作
     *
     * @param element 要插入栈的元素
     * @throws Exception top如果超出dataElements数组大小,称栈上溢出, 抛出异常
     */
    public void push(E element) throws Exception {
        if (top >= dataElements.length) {
            throw new RuntimeException("栈溢出");
        }
        top++;
        dataElements[top] = element;
    }

    /**
     * 栈元素的delete操作
     *
     * @return
     * @throws Exception 空栈做delete操作,称栈下溢出, 抛出异常
     */
    public E pop() {
        if (empty()) {
            throw new RuntimeException("栈下溢出");
        }
        E element = (E) dataElements[this.top];
        top--;
        return element;
    }

    /**
     * top=0时,栈内不包含任务元素,栈为空
     *
     * @return true: 空栈 false: 非空栈
     */
    public boolean empty() {
        return this.top == 0;
    }
}
